package uf1

type UnionFind struct {
	parent []int
	size []int
	count int
}

func (uf *UnionFind) newUnionFind(n int) {
	uf.count = n
	uf.parent = make([]int, n)
	uf.size = make([]int, n)
	for i := 0; i < n; i++ {
		uf.parent[i] = i
		uf.size[i] = 1
	}
}

func (uf *UnionFind) find(p int) int {

	for uf.parent[p] != p  {
		p = uf.parent[p]
	}
	return p
}

func (uf *UnionFind) isConnected(p int, q int) bool {
	return uf.find(p) == uf.find(q)
}

func (uf *UnionFind) union(p int, q int) {
	pRoot := uf.find(p)
	qRoot := uf.find(q)
	if pRoot == qRoot {
		return
	}

	if uf.size[pRoot] < uf.size[qRoot] {
		uf.parent[pRoot] = qRoot
		uf.size[qRoot] += uf.size[pRoot]
	} else {
		uf.parent[qRoot] = pRoot
		uf.size[pRoot] += uf.size[qRoot]
	}
}